#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};



TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
	if (pre.size() == 0)
		return NULL;
	TreeNode *root = new TreeNode(pre[0]);
	if (pre.size() == 1)
		return root;
	vector<int> left_pre,right_pre,left_vin, right_vin;
	vector<int>::iterator rootIter = vin.begin();
	while (*rootIter != pre[0])
		++rootIter;
	left_vin.insert(left_vin.begin(),vin.begin(), rootIter);
	right_vin.insert(right_vin.begin(), rootIter + 1, vin.end());
	left_pre.insert(left_pre.begin(), pre.begin() + 1, pre.begin() + left_vin.size() + 1);
	right_pre.insert(right_pre.begin(), pre.end() - right_vin.size(), pre.end());
	root->left = reConstructBinaryTree(left_pre, left_vin);
	root->right = reConstructBinaryTree(right_pre, right_vin);
	return root;
}

//int main()
//{
//
//	vector<int> pre = { 1,2,4,7,3,5,6,8 }, vin = { 4,7,2,1,5,3,8,6 };
//	TreeNode *root = reConstructBinaryTree(pre, vin);
//	system("pause");
//	return 0;
//
//}